1 Data description

In this tutorial, we aim to obtain differentially expressed genes between two biological conditions in an integrated data. This integrated data set is generated by combining 10 microarray studies on control and TGFb-treated dataset (for more information, see here http://mcr.aacrjournals.org/content/15/5/619). 

First, we assess the presence of unwanted variation in the integrated data which combines differents studies and platforms. Second, we show how to use two RUV methods: RUVinv and RUV4 to remove unwanted variation and detect differentially expressed genes comparing control dataset to TGFb-treated dataset. Third, we assess whether RUV methods are useful and compare the results obtained by each method.

library(ruv)            ## for applying RUV methods
library(limma)          ## for vennDiagram()
library(ggplot2)        ## for data visualisation

The integrated data introduced above have been split into two data sets: dataset A and dataset B, each containing different studies, platforms and tissues. We will explore and normalise these two data sets separately in order to compare the results obtained by the two normalisation methods (RUV4 and RUVinv).

Read in the two integrated dataset.

datasetA<- read.table("expr_10data_datasetA.txt", header = T, sep = "\t")
datasetB<- read.table("expr_10data_datasetB.txt", header = T, sep = "\t")

Look at the data in each dataset A and B, then make a matrix for each these data where the row names are gene IDs.

head(datasetA,3)
head(datasetB,3)
mA<-datasetA[,2:dim(datasetA)[2]]
mB<-datasetB[,2:dim(datasetB)[2]]
row.names(mA)<- datasetA[,1]
row.names(mB)<- datasetB[,1]
mA<- as.matrix(mA)
mB<- as.matrix(mB)

Look at the information related to each dataset including the name of the studies, types of platform, treatment, and tissue:

info_datasetA<- read.table("info_10data_datasetA.txt", sep="\t", header=T)
info_datasetA
info_datasetB<- read.table("info_10data_datasetB.txt", sep="\t", header=T)
info_datasetB

2 Assessment of unwanted variation in the data

Here we perform some exploratory analysis on the integrated data to assess the presence of unwanted variation in each dataset.

2.1 RLE plot

We start by looking at the RLE plots in dataset A data, coloured by study, platform and tissue.For more information about RLE plot see reference paper RLE Plots: Visualising Unwanted Variation in High Dimensional Data, Luke C. Gandolfo, Terence P. Speed 2017.

## Transpose the expression matrix so that we have genes in columns and dataset in rows
YA <- t(mA)
## Plot RLE coloured by study
ruv_rle(YA, info_datasetA$study, ylim = c(-4,4))

## Plot RLE coloured by platform
ruv_rle(YA, info_datasetA$platform, ylim = c(-4,4))

## Plot RLE coloured by platform
ruv_rle(YA, info_datasetA$tissue, ylim = c(-4,4))

Similarly, we look at the RLE plots in dataset B data coloured by study, platform and tissue:

YB <- t(mB)
## Plot RLE coloured by study
ruv_rle(YB, info_datasetB$study, ylim = c(-4,4))

## Plot RLE coloured by platform
ruv_rle(YB, info_datasetB$platform, ylim = c(-4,4))

## Plot RLE coloured by tissue
ruv_rle(YB, info_datasetB$tissue, ylim = c(-4,4))

2.2 PCA plot

In transcriptomics applications, one of the most utilized exploratory plots is the multi-dimensional scaling (MDS) plot or a principal component analysis (PCA) plot. To assess the presence of unwanted variation in each dataset, we use PCA plots to show similarities between dataset measured in an unsupervised way. Ideally, dataset should cluster together according to the treatment (i.e. the biological factor of interest). Here, we see that dataset are rather clustered by studies (i.e. unwanted variation) in both dataset A and B data.
In the current example, it’s important to note that in some cases, different studies are confounded with different platforms and tissues, and therefore there is no way to identify how much of the unwanted variation come from each of these factors. Such situations must be avoided when designing an experiment and for the purpose of this tutorial, we only consider “study” as the source of unwanted variation.

gg_additions <- list(aes(color = info_datasetA$study, 
                         shape = info_datasetA$treatment, 
                         size = 5, alpha = .7),
                     labs(color = "Study", shape="Treatment"),
                     scale_size_identity(guide = "none"),
                     scale_alpha(guide = "none"),
                     theme(legend.text = element_text(size = 12),
                           legend.title = element_text(size = 16)),
                     guides(color = guide_legend(override.aes = list(size = 4)),
                            shape = guide_legend(override.aes = list(size = 4))))
options(repr.plot.width = 8, repr.plot.height = 6)
ruv_svdplot(YA) + gg_additions 

gg_additions <- list(aes(color = info_datasetB$study,
                         shape = info_datasetB$treatment,
                         size = 5, alpha = .7),
                     labs(color = "Study",shape = "Treatment"),
                     scale_size_identity(guide = "none"),
                     scale_alpha(guide = "none"),
                     theme(legend.text = element_text(size = 12),
                           legend.title = element_text(size = 16)),
                     guides(color = guide_legend(override.aes = list(size = 4)),
                            shape = guide_legend(override.aes = list(size = 4))))
options(repr.plot.width=8, repr.plot.height=6)
ruv_svdplot(YB) + gg_additions #

3 Remove batch effects using RUV methods

There are several RUV methods for removing unwanted variation in order to obtain DEGs; these include RUV-2, RUV-4, RUV-inv and RUV-rinv. In general, RUV methods are dependent on negative control genes (genes which are not associated with the biological factor of interest) and replicate dataset (if applicable). RUV-2 removes unwanted variation in two steps. RUV-4 came after RUV-2 and has four steps. For RUV-4 we can estimate the dimension of unwanted variation (k) or select different values for k, while for RUV-inv and RUV-rinv we don’t need to estimate k as it is set to be the maximum value. In general, RUV-inv and RUV-rinv are better than RUV-4. RUV-inv is recommended when we have large number of control genes (~1000), while RUV-rinv is more appropriate with small number of control genes (~60).
Selection of negative control genes is very important. Examples of negative control genes are the spike-in controls or the housekeeping (HK) genes. It is also possible to define empirical negative control genes using an iterative approach. However, it is only recomended if (i) the initial negative control genes are not very good or there are only a few of them; (ii) the beta seems to be very sparse. Therefore, the user needs to generate diagnostic plots to assess the performance of the initial analysis, and only if needed, use an iterative approach to define better control genes.

3.1 RUV4

RUV4 can be run with different values of k in an attempt to find the optimal value. Note that although there is a function to estimate k, called getK(), this may not give the optimal value for k and is often recomended to be used when there is no other choice but to automate finding K (e.g. in simulations).

We begin with the list of housekeeping (HK) genes as our negative controls.

HKgenes <- read.table("HouseKeeping_genes_IDs.txt", header=T, sep="\t")
hk <- HKgenes$GeneID
ctrl <- colnames(YA) %in% hk

3.1.1 Apply RUV4 using house-keeping genes

## Take treatment as the biological factor of interest
groups_A <- factor(info_datasetA$treatment) 
gA <- cbind(as.numeric(groups_A))   ## 1 control, 2: TGFb
## Take treatment as the biological factor of interest
groups_B <- factor(info_datasetB$treatment) 
gB <- cbind(as.numeric(groups_B))   ## 1 control, 2: TGFb
ks <- c(1, 2, 5, 6, 7, 8, 10, 11, 12, 15, 18, 20, 22, 23, 24)
## For k > 24 I got Error:
# NaNs producedNaNs producedError in sigmashrink(fit$sigma2, fit$df) : 
#   NA/NaN/Inf in foreign function call (arg 1)
beta_corAB_HK <- vector()
fit_ruv4_hk_datasetA_all_k=list()
fit_ruv4_hk_datasetA_all_k.summary=list()
fit_ruv4_hk_datasetB_all_k=list()
fit_ruv4_hk_datasetB_all_k.summary=list()
for (K in ks){
  fit_ruv4_hk_datasetA_all_k[[K]] <- RUV4(YA, X = gA, 
                            ctl = ctrl, 
                            k = K,Z = 1, eta = NULL, 
                            fullW0 = NULL, inputcheck = TRUE)
  
  fit_ruv4_hk_datasetA_all_k.summary[[K]] <- ruv_summary(YA,
                                           fit_ruv4_hk_datasetA_all_k[[K]],
                                           info_datasetA)
  
  fit_ruv4_hk_datasetB_all_k[[K]] <- RUV4(YB, X = gB, 
                            ctl = ctrl, 
                            k = K,Z = 1, eta = NULL, 
                            fullW0 = NULL, inputcheck = TRUE)
  
  fit_ruv4_hk_datasetB_all_k.summary[[K]] <- ruv_summary(YB,
                                           fit_ruv4_hk_datasetB_all_k[[K]],
                                           info_datasetB)
  
  currentCor <- cor.test(fit_ruv4_hk_datasetA_all_k[[K]]$betahat,
                        fit_ruv4_hk_datasetB_all_k[[K]]$betahat)$estimate
  
  beta_corAB_HK <- c(beta_corAB_HK, currentCor)
  
}
names(beta_corAB_HK) <- ks
data.frame(beta_corAB_HK) ## K = 23 seems a good choice

4 Comparison of results of unadjusted and RUV4-adjusted data

In order to see if we have helped or not, we run differential expression analysis on the unadjusted data. Then we compare the results of RUV4 with different K values and unadjusted together.

4.1 Unadjusted data

We can run RUV4 with k = 0 to do no adjustment when obtaining DEGs.

4.1.1 Apply DE analysis in the unadjusted data using HK genes

# RUV4 with k = 0 for no adjustment
# Equivalent to a Limma Analysis without considering the batch term
##----- In dataset A data
fit_unadj_hk_datasetA <- RUV4(YA, X = gA, 
                          ctl = ctrl, 
                          k = 0)
fit_unadj_hk_datasetA.summary <- ruv_summary(YA, 
                                        fit_unadj_hk_datasetA,
                                        info_datasetA)
##----- In dataset B data
fit_unadj_hk_datasetB <- RUV4(YB, X = gB, 
                          ctl = ctrl,
                          k = 0)
fit_unadj_hk_datasetB.summary <- ruv_summary(YB, 
                                         fit_unadj_hk_datasetB,
                                         info_datasetB)

4.2 P-values distribution

We compare the results obtained from unajusted, RUVinv- and RUV4- adjusted data using p-value distributions, correlations of beta values and venn diagrams in dataset A and B data.

K=23
ruv_hist(fit_unadj_hk_datasetA.summary) + ggtitle("Unadj_A")

ruv_hist(fit_ruv4_hk_datasetA_all_k.summary[[K]]) + ggtitle("RUV4_HK_A")

ruv_hist(fit_unadj_hk_datasetB.summary) + ggtitle("Unadj_B")

ruv_hist(fit_ruv4_hk_datasetB_all_k.summary[[K]]) + ggtitle("RUV4_HK_B")

4.3 Betahat correlation

For each of the unadjusted, RUVinv- and RUV4- adjusted settings, we can compare the results between dataset A and B data sets to see which method gives more consistent resulst in these two data sets. To quantify these consistencies, we look at the correlations between betahat from dataset A and betahat from dataset B for the unadjusted method, RUVinv and RUV4.

##------ Unadjusted data sets
plot(fit_unadj_hk_datasetA$betahat, 
     fit_unadj_hk_datasetB$betahat,
     xlab = "Betahat dataset A",
     ylab = "Betahat dataset B",
     main = "Unadjusted",
     xlim = c(-3,3), cex = 0.3, ylim = c(-4,4))
corVal <- cor.test(fit_unadj_hk_datasetA$betahat, fit_unadj_hk_datasetB$betahat)$estimate
text(-3,3, pos = 4, paste("Correlation: ", round(corVal,2), sep = ""))

for (K in ks){
   
  #------- RUV4 adjusted data sets
  plot(fit_ruv4_hk_datasetA_all_k[[K]]$betahat,
     fit_ruv4_hk_datasetB_all_k[[K]]$betahat,
     xlab = "Betahat dataset A",
     ylab = "Betahat dataset B",
     main = paste("RUV4_K_",K,sep=""),
     xlim = c(-3,3), cex = 0.3, ylim = c(-4,4))
  #abline(fit_ruv4_emp_datasetB$betahat,fit_ruv4_emp_datasetA$betahat)
  corVal <- cor.test(fit_ruv4_hk_datasetA_all_k[[K]]$betahat, fit_ruv4_hk_datasetB_all_k[[K]]$betahat)$estimate
  text(-3,3, pos=4, paste("Correlation: ", round(corVal,2),sep=""))
}

4.4 Overlap between differentially expressed genes

Finally, for each of the unadjusted, RUVinv and RUV4, we look at the number of overlapping differentially expressed genes (DEGs) between the two dataset A and B data sets. We also check for consistency between methods on the same data (dataset A or dataset B data set).
First, we define DEGs as genes with adjusted p-value < 0.05 and |logFC| > 1 in dataset A and B data sets which are unadjusted, RUV4- or RUVinv-adjusted.

##------ In dataset A data
DEGsUnadj_datasetA <- row.names(fit_unadj_hk_datasetA.summary$C)[fit_unadj_hk_datasetA.summary$C$F.p.BH < 0.05 & abs(fit_unadj_hk_datasetA.summary$C$b_X1) > 1]
DEGsRUV4_datasetA <- row.names(fit_ruv4_hk_datasetA.summary$C)[fit_ruv4_hk_datasetA.summary$C$F.p.BH < 0.05 & abs(fit_ruv4_hk_datasetA.summary$C$b_X1) > 1]  
Error in row.names(fit_ruv4_hk_datasetA.summary$C) : 
  object 'fit_ruv4_hk_datasetA.summary' not found

4.4.1 DEGs in the unadjusted data

Venn diagram comparing the unadjusted dataset A and B data.

4.4.2 DEGs in the RUV4-adjusted data for different k

Venn diagram comparing the RUV4-adjusted dataset A and B data.

4.4.3 Compare the unadjusted and RUV4 in dataset A data

4.4.4 Compare the unadjusted and RUV4 in dataset B data

LS0tCnRpdGxlOiAiSG93IHRvIHJlbW92ZSB1bndhbnRlZCB2YXJpYXRpb24gZnJvbSB0cmFuc2NyaXB0b21pY3MgZGF0YSB1c2luZyBSVVZpbnYgYW5kIFJVVjQiCmF1dGhvcjogU2VwaWRlaCBGb3JvdXRhbiBhbmQgTWFyaWUgVHJ1c3NhcnQKb3V0cHV0OgogIGdpdGh1Yl9kb2N1bWVudDoKICAgIHRvYzogeWVzCiAgaHRtbF9ub3RlYm9vazoKICAgIG51bWJlcl9zZWN0aW9uczogeWVzCiAgICB0b2M6IHllcwogICAgdG9jX2Zsb2F0OiB5ZXMKICAgIGNvZGVfZm9sZGluZzogImhpZGUiCiAgICBmaWdfY2FwdGlvbjogeWVzCi0tLQoKCiMgRGF0YSBkZXNjcmlwdGlvbgpJbiB0aGlzIHR1dG9yaWFsLCB3ZSBhaW0gdG8gb2J0YWluIGRpZmZlcmVudGlhbGx5IGV4cHJlc3NlZCBnZW5lcyBiZXR3ZWVuIHR3byBiaW9sb2dpY2FsIGNvbmRpdGlvbnMgaW4gYW4gaW50ZWdyYXRlZCBkYXRhLiBUaGlzIGludGVncmF0ZWQgZGF0YSBzZXQgaXMgZ2VuZXJhdGVkIGJ5IGNvbWJpbmluZyAxMCBtaWNyb2FycmF5IHN0dWRpZXMgb24gY29udHJvbCBhbmQgVEdGYi10cmVhdGVkIGRhdGFzZXQgKGZvciBtb3JlIGluZm9ybWF0aW9uLCBzZWUgaGVyZSBodHRwOi8vbWNyLmFhY3Jqb3VybmFscy5vcmcvY29udGVudC8xNS81LzYxOSkuXCAKCkZpcnN0LCB3ZSBhc3Nlc3MgdGhlIHByZXNlbmNlIG9mIHVud2FudGVkIHZhcmlhdGlvbiBpbiB0aGUgaW50ZWdyYXRlZCBkYXRhIHdoaWNoIGNvbWJpbmVzIGRpZmZlcmVudHMgc3R1ZGllcyBhbmQgcGxhdGZvcm1zLiBTZWNvbmQsIHdlIHNob3cgaG93IHRvIHVzZSB0d28gUlVWIG1ldGhvZHM6IFJVVmludiBhbmQgUlVWNCB0byByZW1vdmUgdW53YW50ZWQgdmFyaWF0aW9uIGFuZCBkZXRlY3QgZGlmZmVyZW50aWFsbHkgZXhwcmVzc2VkIGdlbmVzIGNvbXBhcmluZyBjb250cm9sIGRhdGFzZXQgdG8gVEdGYi10cmVhdGVkIGRhdGFzZXQuIFRoaXJkLCB3ZSBhc3Nlc3Mgd2hldGhlciBSVVYgbWV0aG9kcyBhcmUgdXNlZnVsIGFuZCBjb21wYXJlIHRoZSByZXN1bHRzIG9idGFpbmVkIGJ5IGVhY2ggbWV0aG9kLgpgYGB7ciBsb2FkLWxpYnN9CmxpYnJhcnkocnV2KSAgICAgICAgICAgICMjIGZvciBhcHBseWluZyBSVVYgbWV0aG9kcwpsaWJyYXJ5KGxpbW1hKSAgICAgICAgICAjIyBmb3IgdmVubkRpYWdyYW0oKQpsaWJyYXJ5KGdncGxvdDIpICAgICAgICAjIyBmb3IgZGF0YSB2aXN1YWxpc2F0aW9uCmBgYAoKVGhlIGludGVncmF0ZWQgZGF0YSBpbnRyb2R1Y2VkIGFib3ZlIGhhdmUgYmVlbiBzcGxpdCBpbnRvIHR3byBkYXRhIHNldHM6IGRhdGFzZXQgQSBhbmQgZGF0YXNldCBCLCBlYWNoIGNvbnRhaW5pbmcgZGlmZmVyZW50IHN0dWRpZXMsIHBsYXRmb3JtcyBhbmQgdGlzc3Vlcy4gV2Ugd2lsbCBleHBsb3JlIGFuZCBub3JtYWxpc2UgdGhlc2UgdHdvIGRhdGEgc2V0cyBzZXBhcmF0ZWx5IGluIG9yZGVyIHRvIGNvbXBhcmUgdGhlIHJlc3VsdHMgb2J0YWluZWQgYnkgdGhlIHR3byBub3JtYWxpc2F0aW9uIG1ldGhvZHMgKFJVVjQgYW5kIFJVVmludikuCgpSZWFkIGluIHRoZSB0d28gaW50ZWdyYXRlZCBkYXRhc2V0LgpgYGB7ciBsb2FkLWRhdGF9CmRhdGFzZXRBPC0gcmVhZC50YWJsZSgiZXhwcl8xMGRhdGFfZGF0YXNldEEudHh0IiwgaGVhZGVyID0gVCwgc2VwID0gIlx0IikKZGF0YXNldEI8LSByZWFkLnRhYmxlKCJleHByXzEwZGF0YV9kYXRhc2V0Qi50eHQiLCBoZWFkZXIgPSBULCBzZXAgPSAiXHQiKQpgYGAKCkxvb2sgYXQgdGhlIGRhdGEgaW4gZWFjaCBkYXRhc2V0IEEgYW5kIEIsIHRoZW4gbWFrZSBhIG1hdHJpeCBmb3IgZWFjaCB0aGVzZSBkYXRhIHdoZXJlIHRoZSByb3cgbmFtZXMgYXJlIGdlbmUgSURzLgpgYGB7ciBleHBsb3JlLWRhdGF9CgpoZWFkKGRhdGFzZXRBLDMpCmhlYWQoZGF0YXNldEIsMykKbUE8LWRhdGFzZXRBWywyOmRpbShkYXRhc2V0QSlbMl1dCm1CPC1kYXRhc2V0QlssMjpkaW0oZGF0YXNldEIpWzJdXQpyb3cubmFtZXMobUEpPC0gZGF0YXNldEFbLDFdCnJvdy5uYW1lcyhtQik8LSBkYXRhc2V0QlssMV0KbUE8LSBhcy5tYXRyaXgobUEpCm1CPC0gYXMubWF0cml4KG1CKQpgYGAKCkxvb2sgYXQgdGhlIGluZm9ybWF0aW9uIHJlbGF0ZWQgdG8gZWFjaCBkYXRhc2V0IGluY2x1ZGluZyB0aGUgbmFtZSBvZiB0aGUgc3R1ZGllcywgdHlwZXMgb2YgcGxhdGZvcm0sIHRyZWF0bWVudCwgYW5kIHRpc3N1ZToKYGBge3IgbG9hZC1pbmZvLXN0dWR5fQppbmZvX2RhdGFzZXRBPC0gcmVhZC50YWJsZSgiaW5mb18xMGRhdGFfZGF0YXNldEEudHh0Iiwgc2VwPSJcdCIsIGhlYWRlcj1UKQppbmZvX2RhdGFzZXRBCmluZm9fZGF0YXNldEI8LSByZWFkLnRhYmxlKCJpbmZvXzEwZGF0YV9kYXRhc2V0Qi50eHQiLCBzZXA9Ilx0IiwgaGVhZGVyPVQpCmluZm9fZGF0YXNldEIKYGBgCgojIEFzc2Vzc21lbnQgb2YgdW53YW50ZWQgdmFyaWF0aW9uIGluIHRoZSBkYXRhCkhlcmUgd2UgcGVyZm9ybSBzb21lIGV4cGxvcmF0b3J5IGFuYWx5c2lzIG9uIHRoZSBpbnRlZ3JhdGVkIGRhdGEgdG8gYXNzZXNzIHRoZSBwcmVzZW5jZSBvZiB1bndhbnRlZCB2YXJpYXRpb24gaW4gZWFjaCBkYXRhc2V0LgoKIyMgUkxFIHBsb3QKV2Ugc3RhcnQgYnkgbG9va2luZyBhdCB0aGUgUkxFIHBsb3RzIGluIGRhdGFzZXQgQSBkYXRhLCBjb2xvdXJlZCBieSBzdHVkeSwgcGxhdGZvcm0gYW5kIHRpc3N1ZS5Gb3IgbW9yZSBpbmZvcm1hdGlvbiBhYm91dCBSTEUgcGxvdCBzZWUgcmVmZXJlbmNlIHBhcGVyIFtSTEUgUGxvdHM6IFZpc3VhbGlzaW5nIFVud2FudGVkIFZhcmlhdGlvbiBpbiBIaWdoIERpbWVuc2lvbmFsIERhdGFdKGh0dHBzOi8vYXJ4aXYub3JnL2Ficy8xNzA0LjAzNTkwKSwgTHVrZSBDLiBHYW5kb2xmbywgVGVyZW5jZSBQLiBTcGVlZCAyMDE3LgoKYGBge3IgcmxlcGxvdHMtZGF0YXNldEF9CiMjIFRyYW5zcG9zZSB0aGUgZXhwcmVzc2lvbiBtYXRyaXggc28gdGhhdCB3ZSBoYXZlIGdlbmVzIGluIGNvbHVtbnMgYW5kIGRhdGFzZXQgaW4gcm93cwpZQSA8LSB0KG1BKQojIyBQbG90IFJMRSBjb2xvdXJlZCBieSBzdHVkeQpydXZfcmxlKFlBLCBpbmZvX2RhdGFzZXRBJHN0dWR5LCB5bGltID0gYygtNCw0KSkKIyMgUGxvdCBSTEUgY29sb3VyZWQgYnkgcGxhdGZvcm0KcnV2X3JsZShZQSwgaW5mb19kYXRhc2V0QSRwbGF0Zm9ybSwgeWxpbSA9IGMoLTQsNCkpCiMjIFBsb3QgUkxFIGNvbG91cmVkIGJ5IHBsYXRmb3JtCnJ1dl9ybGUoWUEsIGluZm9fZGF0YXNldEEkdGlzc3VlLCB5bGltID0gYygtNCw0KSkKYGBgCgpTaW1pbGFybHksIHdlIGxvb2sgYXQgdGhlIFJMRSBwbG90cyBpbiBkYXRhc2V0IEIgZGF0YSBjb2xvdXJlZCBieSBzdHVkeSwgcGxhdGZvcm0gYW5kIHRpc3N1ZToKYGBge3IgcmxlcGxvdHMtZGF0YXNldEJ9CllCIDwtIHQobUIpCiMjIFBsb3QgUkxFIGNvbG91cmVkIGJ5IHN0dWR5CnJ1dl9ybGUoWUIsIGluZm9fZGF0YXNldEIkc3R1ZHksIHlsaW0gPSBjKC00LDQpKQojIyBQbG90IFJMRSBjb2xvdXJlZCBieSBwbGF0Zm9ybQpydXZfcmxlKFlCLCBpbmZvX2RhdGFzZXRCJHBsYXRmb3JtLCB5bGltID0gYygtNCw0KSkKIyMgUGxvdCBSTEUgY29sb3VyZWQgYnkgdGlzc3VlCnJ1dl9ybGUoWUIsIGluZm9fZGF0YXNldEIkdGlzc3VlLCB5bGltID0gYygtNCw0KSkKYGBgCgojIyBQQ0EgcGxvdApJbiB0cmFuc2NyaXB0b21pY3MgYXBwbGljYXRpb25zLCBvbmUgb2YgdGhlIG1vc3QgdXRpbGl6ZWQgZXhwbG9yYXRvcnkgcGxvdHMgaXMgdGhlIG11bHRpLWRpbWVuc2lvbmFsIHNjYWxpbmcgKE1EUykgcGxvdCBvciBhIHByaW5jaXBhbCBjb21wb25lbnQgYW5hbHlzaXMgKFBDQSkgcGxvdC4gVG8gYXNzZXNzIHRoZSBwcmVzZW5jZSBvZiB1bndhbnRlZCB2YXJpYXRpb24gaW4gZWFjaCBkYXRhc2V0LCB3ZSB1c2UgUENBIHBsb3RzIHRvIHNob3cgc2ltaWxhcml0aWVzIGJldHdlZW4gZGF0YXNldCBtZWFzdXJlZCBpbiBhbiB1bnN1cGVydmlzZWQgd2F5LiBJZGVhbGx5LCBkYXRhc2V0IHNob3VsZCBjbHVzdGVyIHRvZ2V0aGVyIGFjY29yZGluZyB0byB0aGUgdHJlYXRtZW50IChpLmUuIHRoZSBiaW9sb2dpY2FsIGZhY3RvciBvZiBpbnRlcmVzdCkuIEhlcmUsIHdlIHNlZSB0aGF0IGRhdGFzZXQgYXJlIHJhdGhlciBjbHVzdGVyZWQgYnkgc3R1ZGllcyAoaS5lLiB1bndhbnRlZCB2YXJpYXRpb24pIGluIGJvdGggZGF0YXNldCBBIGFuZCBCIGRhdGEuXApJbiB0aGUgY3VycmVudCBleGFtcGxlLCBpdCdzIGltcG9ydGFudCB0byBub3RlIHRoYXQgaW4gc29tZSBjYXNlcywgZGlmZmVyZW50IHN0dWRpZXMgYXJlIGNvbmZvdW5kZWQgd2l0aCBkaWZmZXJlbnQgcGxhdGZvcm1zIGFuZCB0aXNzdWVzLCBhbmQgdGhlcmVmb3JlIHRoZXJlIGlzIG5vIHdheSB0byBpZGVudGlmeSBob3cgbXVjaCBvZiB0aGUgdW53YW50ZWQgdmFyaWF0aW9uIGNvbWUgZnJvbSBlYWNoIG9mIHRoZXNlIGZhY3RvcnMuIFN1Y2ggc2l0dWF0aW9ucyBtdXN0IGJlIGF2b2lkZWQgd2hlbiBkZXNpZ25pbmcgYW4gZXhwZXJpbWVudCBhbmQgZm9yIHRoZSBwdXJwb3NlIG9mIHRoaXMgdHV0b3JpYWwsIHdlIG9ubHkgY29uc2lkZXIgInN0dWR5IiBhcyB0aGUgc291cmNlIG9mIHVud2FudGVkIHZhcmlhdGlvbi5cCgpgYGB7ciBtZHMtcGxvdC1kYXRhc2V0QX0KZ2dfYWRkaXRpb25zIDwtIGxpc3QoYWVzKGNvbG9yID0gaW5mb19kYXRhc2V0QSRzdHVkeSwgCiAgICAgICAgICAgICAgICAgICAgICAgICBzaGFwZSA9IGluZm9fZGF0YXNldEEkdHJlYXRtZW50LCAKICAgICAgICAgICAgICAgICAgICAgICAgIHNpemUgPSA1LCBhbHBoYSA9IC43KSwKICAgICAgICAgICAgICAgICAgICAgbGFicyhjb2xvciA9ICJTdHVkeSIsIHNoYXBlPSJUcmVhdG1lbnQiKSwKICAgICAgICAgICAgICAgICAgICAgc2NhbGVfc2l6ZV9pZGVudGl0eShndWlkZSA9ICJub25lIiksCiAgICAgICAgICAgICAgICAgICAgIHNjYWxlX2FscGhhKGd1aWRlID0gIm5vbmUiKSwKICAgICAgICAgICAgICAgICAgICAgdGhlbWUobGVnZW5kLnRleHQgPSBlbGVtZW50X3RleHQoc2l6ZSA9IDEyKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgbGVnZW5kLnRpdGxlID0gZWxlbWVudF90ZXh0KHNpemUgPSAxNikpLAogICAgICAgICAgICAgICAgICAgICBndWlkZXMoY29sb3IgPSBndWlkZV9sZWdlbmQob3ZlcnJpZGUuYWVzID0gbGlzdChzaXplID0gNCkpLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgc2hhcGUgPSBndWlkZV9sZWdlbmQob3ZlcnJpZGUuYWVzID0gbGlzdChzaXplID0gNCkpKSkKb3B0aW9ucyhyZXByLnBsb3Qud2lkdGggPSA4LCByZXByLnBsb3QuaGVpZ2h0ID0gNikKcnV2X3N2ZHBsb3QoWUEpICsgZ2dfYWRkaXRpb25zIApgYGAKCmBgYHtyIG1kcy1wbG90LWRhdGFzZXRCfQpnZ19hZGRpdGlvbnMgPC0gbGlzdChhZXMoY29sb3IgPSBpbmZvX2RhdGFzZXRCJHN0dWR5LAogICAgICAgICAgICAgICAgICAgICAgICAgc2hhcGUgPSBpbmZvX2RhdGFzZXRCJHRyZWF0bWVudCwKICAgICAgICAgICAgICAgICAgICAgICAgIHNpemUgPSA1LCBhbHBoYSA9IC43KSwKICAgICAgICAgICAgICAgICAgICAgbGFicyhjb2xvciA9ICJTdHVkeSIsc2hhcGUgPSAiVHJlYXRtZW50IiksCiAgICAgICAgICAgICAgICAgICAgIHNjYWxlX3NpemVfaWRlbnRpdHkoZ3VpZGUgPSAibm9uZSIpLAogICAgICAgICAgICAgICAgICAgICBzY2FsZV9hbHBoYShndWlkZSA9ICJub25lIiksCiAgICAgICAgICAgICAgICAgICAgIHRoZW1lKGxlZ2VuZC50ZXh0ID0gZWxlbWVudF90ZXh0KHNpemUgPSAxMiksCiAgICAgICAgICAgICAgICAgICAgICAgICAgIGxlZ2VuZC50aXRsZSA9IGVsZW1lbnRfdGV4dChzaXplID0gMTYpKSwKICAgICAgICAgICAgICAgICAgICAgZ3VpZGVzKGNvbG9yID0gZ3VpZGVfbGVnZW5kKG92ZXJyaWRlLmFlcyA9IGxpc3Qoc2l6ZSA9IDQpKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgIHNoYXBlID0gZ3VpZGVfbGVnZW5kKG92ZXJyaWRlLmFlcyA9IGxpc3Qoc2l6ZSA9IDQpKSkpCm9wdGlvbnMocmVwci5wbG90LndpZHRoPTgsIHJlcHIucGxvdC5oZWlnaHQ9NikKcnV2X3N2ZHBsb3QoWUIpICsgZ2dfYWRkaXRpb25zICMKYGBgCgoKIyBSZW1vdmUgYmF0Y2ggZWZmZWN0cyB1c2luZyBSVVYgbWV0aG9kcwpUaGVyZSBhcmUgc2V2ZXJhbCBSVVYgbWV0aG9kcyBmb3IgcmVtb3ZpbmcgdW53YW50ZWQgdmFyaWF0aW9uIGluIG9yZGVyIHRvIG9idGFpbiBERUdzOyB0aGVzZSBpbmNsdWRlIFJVVi0yLCBSVVYtNCwgUlVWLWludiBhbmQgUlVWLXJpbnYuIEluIGdlbmVyYWwsIFJVViBtZXRob2RzIGFyZSBkZXBlbmRlbnQgb24gbmVnYXRpdmUgY29udHJvbCBnZW5lcyAoZ2VuZXMgd2hpY2ggYXJlIG5vdCBhc3NvY2lhdGVkIHdpdGggdGhlIGJpb2xvZ2ljYWwgZmFjdG9yIG9mIGludGVyZXN0KSBhbmQgcmVwbGljYXRlIGRhdGFzZXQgKGlmIGFwcGxpY2FibGUpLiBSVVYtMiByZW1vdmVzIHVud2FudGVkIHZhcmlhdGlvbiBpbiB0d28gc3RlcHMuIFJVVi00IGNhbWUgYWZ0ZXIgUlVWLTIgYW5kIGhhcyBmb3VyIHN0ZXBzLiBGb3IgUlVWLTQgd2UgY2FuIGVzdGltYXRlIHRoZSBkaW1lbnNpb24gb2YgdW53YW50ZWQgdmFyaWF0aW9uIChrKSBvciBzZWxlY3QgZGlmZmVyZW50IHZhbHVlcyBmb3Igaywgd2hpbGUgZm9yIFJVVi1pbnYgYW5kIFJVVi1yaW52IHdlIGRvbid0IG5lZWQgdG8gZXN0aW1hdGUgayBhcyBpdCBpcyBzZXQgdG8gYmUgdGhlIG1heGltdW0gdmFsdWUuIEluIGdlbmVyYWwsIFJVVi1pbnYgYW5kIFJVVi1yaW52IGFyZSBiZXR0ZXIgdGhhbiBSVVYtNC4gUlVWLWludiBpcyByZWNvbW1lbmRlZCB3aGVuIHdlIGhhdmUgbGFyZ2UgbnVtYmVyIG9mIGNvbnRyb2wgZ2VuZXMgKH4xMDAwKSwgd2hpbGUgUlVWLXJpbnYgaXMgbW9yZSBhcHByb3ByaWF0ZSB3aXRoIHNtYWxsIG51bWJlciBvZiBjb250cm9sIGdlbmVzICh+NjApLlwKClNlbGVjdGlvbiBvZiBuZWdhdGl2ZSBjb250cm9sIGdlbmVzIGlzIHZlcnkgaW1wb3J0YW50LiBFeGFtcGxlcyBvZiBuZWdhdGl2ZSBjb250cm9sIGdlbmVzIGFyZSB0aGUgc3Bpa2UtaW4gY29udHJvbHMgb3IgdGhlIGhvdXNla2VlcGluZyAoSEspIGdlbmVzLiBJdCBpcyBhbHNvIHBvc3NpYmxlIHRvIGRlZmluZSBlbXBpcmljYWwgbmVnYXRpdmUgY29udHJvbCBnZW5lcyB1c2luZyBhbiBpdGVyYXRpdmUgYXBwcm9hY2guIEhvd2V2ZXIsIGl0IGlzIG9ubHkgcmVjb21lbmRlZCBpZiAoaSkgdGhlIGluaXRpYWwgbmVnYXRpdmUgY29udHJvbCBnZW5lcyBhcmUgbm90IHZlcnkgZ29vZCBvciB0aGVyZSBhcmUgb25seSBhIGZldyBvZiB0aGVtOyAoaWkpIHRoZSBiZXRhIHNlZW1zIHRvIGJlIHZlcnkgc3BhcnNlLiBUaGVyZWZvcmUsIHRoZSB1c2VyIG5lZWRzIHRvIGdlbmVyYXRlIGRpYWdub3N0aWMgcGxvdHMgdG8gYXNzZXNzIHRoZSBwZXJmb3JtYW5jZSBvZiB0aGUgaW5pdGlhbCBhbmFseXNpcywgYW5kIG9ubHkgaWYgbmVlZGVkLCB1c2UgYW4gaXRlcmF0aXZlIGFwcHJvYWNoIHRvIGRlZmluZSBiZXR0ZXIgY29udHJvbCBnZW5lcy4KCgojIyBSVVY0ClJVVjQgY2FuIGJlIHJ1biB3aXRoIGRpZmZlcmVudCB2YWx1ZXMgb2YgayBpbiBhbiBhdHRlbXB0IHRvIGZpbmQgdGhlIG9wdGltYWwgdmFsdWUuIE5vdGUgdGhhdCBhbHRob3VnaCB0aGVyZSBpcyBhIGZ1bmN0aW9uIHRvIGVzdGltYXRlIGssIGNhbGxlZCAqKmdldEsoKSoqLCB0aGlzIG1heSBub3QgZ2l2ZSB0aGUgb3B0aW1hbCB2YWx1ZSBmb3IgayBhbmQgaXMgb2Z0ZW4gcmVjb21lbmRlZCB0byBiZSB1c2VkIHdoZW4gdGhlcmUgaXMgbm8gb3RoZXIgY2hvaWNlIGJ1dCB0byBhdXRvbWF0ZSBmaW5kaW5nIEsgKGUuZy4gaW4gc2ltdWxhdGlvbnMpLiAKCldlIGJlZ2luIHdpdGggdGhlIGxpc3Qgb2YgaG91c2VrZWVwaW5nIChISykgZ2VuZXMgYXMgb3VyIG5lZ2F0aXZlIGNvbnRyb2xzLgpgYGB7cn0KSEtnZW5lcyA8LSByZWFkLnRhYmxlKCJIb3VzZUtlZXBpbmdfZ2VuZXNfSURzLnR4dCIsIGhlYWRlcj1ULCBzZXA9Ilx0IikKaGsgPC0gSEtnZW5lcyRHZW5lSUQKY3RybCA8LSBjb2xuYW1lcyhZQSkgJWluJSBoawpgYGAKCgojIyMgQXBwbHkgUlVWNCB1c2luZyBob3VzZS1rZWVwaW5nIGdlbmVzCmBgYCB7ciBydXY0LUhLLWRpZmZlcmVudEtzfQojIyBUYWtlIHRyZWF0bWVudCBhcyB0aGUgYmlvbG9naWNhbCBmYWN0b3Igb2YgaW50ZXJlc3QKZ3JvdXBzX0EgPC0gZmFjdG9yKGluZm9fZGF0YXNldEEkdHJlYXRtZW50KSAKZ0EgPC0gY2JpbmQoYXMubnVtZXJpYyhncm91cHNfQSkpICAgIyMgMSBjb250cm9sLCAyOiBUR0ZiCiMjIFRha2UgdHJlYXRtZW50IGFzIHRoZSBiaW9sb2dpY2FsIGZhY3RvciBvZiBpbnRlcmVzdApncm91cHNfQiA8LSBmYWN0b3IoaW5mb19kYXRhc2V0QiR0cmVhdG1lbnQpIApnQiA8LSBjYmluZChhcy5udW1lcmljKGdyb3Vwc19CKSkgICAjIyAxIGNvbnRyb2wsIDI6IFRHRmIKCmtzIDwtIGMoMSwgMiwgNSwgNiwgNywgOCwgMTAsIDExLCAxMiwgMTUsIDE4LCAyMCwgMjIsIDIzLCAyNCkKIyMgRm9yIGsgPiAyNCBJIGdvdCBFcnJvcjoKIyBOYU5zIHByb2R1Y2VkTmFOcyBwcm9kdWNlZEVycm9yIGluIHNpZ21hc2hyaW5rKGZpdCRzaWdtYTIsIGZpdCRkZikgOiAKIyAgIE5BL05hTi9JbmYgaW4gZm9yZWlnbiBmdW5jdGlvbiBjYWxsIChhcmcgMSkKCmJldGFfY29yQUJfSEsgPC0gdmVjdG9yKCkKZml0X3J1djRfaGtfZGF0YXNldEFfYWxsX2s9bGlzdCgpCmZpdF9ydXY0X2hrX2RhdGFzZXRBX2FsbF9rLnN1bW1hcnk9bGlzdCgpCmZpdF9ydXY0X2hrX2RhdGFzZXRCX2FsbF9rPWxpc3QoKQpmaXRfcnV2NF9oa19kYXRhc2V0Ql9hbGxfay5zdW1tYXJ5PWxpc3QoKQpmb3IgKEsgaW4ga3MpewogIGZpdF9ydXY0X2hrX2RhdGFzZXRBX2FsbF9rW1tLXV0gPC0gUlVWNChZQSwgWCA9IGdBLCAKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGN0bCA9IGN0cmwsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgayA9IEssWiA9IDEsIGV0YSA9IE5VTEwsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgZnVsbFcwID0gTlVMTCwgaW5wdXRjaGVjayA9IFRSVUUpCiAgCiAgZml0X3J1djRfaGtfZGF0YXNldEFfYWxsX2suc3VtbWFyeVtbS11dIDwtIHJ1dl9zdW1tYXJ5KFlBLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZml0X3J1djRfaGtfZGF0YXNldEFfYWxsX2tbW0tdXSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGluZm9fZGF0YXNldEEpCiAgCiAgZml0X3J1djRfaGtfZGF0YXNldEJfYWxsX2tbW0tdXSA8LSBSVVY0KFlCLCBYID0gZ0IsIAogICAgICAgICAgICAgICAgICAgICAgICAgICAgY3RsID0gY3RybCwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBrID0gSyxaID0gMSwgZXRhID0gTlVMTCwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBmdWxsVzAgPSBOVUxMLCBpbnB1dGNoZWNrID0gVFJVRSkKICAKICBmaXRfcnV2NF9oa19kYXRhc2V0Ql9hbGxfay5zdW1tYXJ5W1tLXV0gPC0gcnV2X3N1bW1hcnkoWUIsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBmaXRfcnV2NF9oa19kYXRhc2V0Ql9hbGxfa1tbS11dLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgaW5mb19kYXRhc2V0QikKICAKICBjdXJyZW50Q29yIDwtIGNvci50ZXN0KGZpdF9ydXY0X2hrX2RhdGFzZXRBX2FsbF9rW1tLXV0kYmV0YWhhdCwKICAgICAgICAgICAgICAgICAgICAgICAgZml0X3J1djRfaGtfZGF0YXNldEJfYWxsX2tbW0tdXSRiZXRhaGF0KSRlc3RpbWF0ZQogIAogIGJldGFfY29yQUJfSEsgPC0gYyhiZXRhX2NvckFCX0hLLCBjdXJyZW50Q29yKQogIAp9Cm5hbWVzKGJldGFfY29yQUJfSEspIDwtIGtzCmRhdGEuZnJhbWUoYmV0YV9jb3JBQl9ISykgIyMgSyA9IDIzIHNlZW1zIGEgZ29vZCBjaG9pY2UKYGBgCgojIENvbXBhcmlzb24gb2YgcmVzdWx0cyBvZiB1bmFkanVzdGVkIGFuZCBSVVY0LWFkanVzdGVkIGRhdGEKSW4gb3JkZXIgdG8gc2VlIGlmIHdlIGhhdmUgaGVscGVkIG9yIG5vdCwgd2UgcnVuIGRpZmZlcmVudGlhbCBleHByZXNzaW9uIGFuYWx5c2lzIG9uIHRoZSAqKnVuYWRqdXN0ZWQgZGF0YSoqLiBUaGVuIHdlIGNvbXBhcmUgdGhlIHJlc3VsdHMgb2YgUlVWNCB3aXRoIGRpZmZlcmVudCBLIHZhbHVlcyBhbmQgdW5hZGp1c3RlZCB0b2dldGhlci4KCiMjIFVuYWRqdXN0ZWQgZGF0YQpXZSBjYW4gcnVuIFJVVjQgd2l0aCBrID0gMCB0byBkbyBubyBhZGp1c3RtZW50IHdoZW4gb2J0YWluaW5nIERFR3MuCgojIyMgQXBwbHkgREUgYW5hbHlzaXMgaW4gdGhlIHVuYWRqdXN0ZWQgZGF0YSB1c2luZyBISyBnZW5lcwpgYGB7ciBERS11bmFkanVzdGVkLUEtQi11c2luZy1IS30KIyBSVVY0IHdpdGggayA9IDAgZm9yIG5vIGFkanVzdG1lbnQKIyBFcXVpdmFsZW50IHRvIGEgTGltbWEgQW5hbHlzaXMgd2l0aG91dCBjb25zaWRlcmluZyB0aGUgYmF0Y2ggdGVybQojIy0tLS0tIEluIGRhdGFzZXQgQSBkYXRhCmZpdF91bmFkal9oa19kYXRhc2V0QSA8LSBSVVY0KFlBLCBYID0gZ0EsIAogICAgICAgICAgICAgICAgICAgICAgICAgIGN0bCA9IGN0cmwsIAogICAgICAgICAgICAgICAgICAgICAgICAgIGsgPSAwKQpmaXRfdW5hZGpfaGtfZGF0YXNldEEuc3VtbWFyeSA8LSBydXZfc3VtbWFyeShZQSwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBmaXRfdW5hZGpfaGtfZGF0YXNldEEsCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBpbmZvX2RhdGFzZXRBKQoKIyMtLS0tLSBJbiBkYXRhc2V0IEIgZGF0YQpmaXRfdW5hZGpfaGtfZGF0YXNldEIgPC0gUlVWNChZQiwgWCA9IGdCLCAKICAgICAgICAgICAgICAgICAgICAgICAgICBjdGwgPSBjdHJsLAogICAgICAgICAgICAgICAgICAgICAgICAgIGsgPSAwKQpmaXRfdW5hZGpfaGtfZGF0YXNldEIuc3VtbWFyeSA8LSBydXZfc3VtbWFyeShZQiwgCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgZml0X3VuYWRqX2hrX2RhdGFzZXRCLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIGluZm9fZGF0YXNldEIpCgpgYGAKCiMjIFAtdmFsdWVzIGRpc3RyaWJ1dGlvbgpXZSBjb21wYXJlIHRoZSByZXN1bHRzIG9idGFpbmVkIGZyb20gdW5hanVzdGVkLCBSVVZpbnYtIGFuZCBSVVY0LSBhZGp1c3RlZCBkYXRhIHVzaW5nIHAtdmFsdWUgZGlzdHJpYnV0aW9ucywgY29ycmVsYXRpb25zIG9mIGJldGEgdmFsdWVzIGFuZCB2ZW5uIGRpYWdyYW1zIGluIGRhdGFzZXQgQSBhbmQgQiBkYXRhLgoKYGBge3J9Cks9MjMKcnV2X2hpc3QoZml0X3VuYWRqX2hrX2RhdGFzZXRBLnN1bW1hcnkpICsgZ2d0aXRsZSgiVW5hZGpfQSIpCnJ1dl9oaXN0KGZpdF9ydXY0X2hrX2RhdGFzZXRBX2FsbF9rLnN1bW1hcnlbW0tdXSkgKyBnZ3RpdGxlKCJSVVY0X0hLX0EiKQoKcnV2X2hpc3QoZml0X3VuYWRqX2hrX2RhdGFzZXRCLnN1bW1hcnkpICsgZ2d0aXRsZSgiVW5hZGpfQiIpCnJ1dl9oaXN0KGZpdF9ydXY0X2hrX2RhdGFzZXRCX2FsbF9rLnN1bW1hcnlbW0tdXSkgKyBnZ3RpdGxlKCJSVVY0X0hLX0IiKQpgYGAKCiMjIEJldGFoYXQgY29ycmVsYXRpb24KRm9yIGVhY2ggb2YgdGhlIHVuYWRqdXN0ZWQsIFJVVmludi0gYW5kIFJVVjQtIGFkanVzdGVkIHNldHRpbmdzLCB3ZSBjYW4gY29tcGFyZSB0aGUgcmVzdWx0cyBiZXR3ZWVuIGRhdGFzZXQgQSBhbmQgQiBkYXRhIHNldHMgdG8gc2VlIHdoaWNoIG1ldGhvZCBnaXZlcyBtb3JlIGNvbnNpc3RlbnQgcmVzdWxzdCBpbiB0aGVzZSB0d28gZGF0YSBzZXRzLiBUbyBxdWFudGlmeSB0aGVzZSBjb25zaXN0ZW5jaWVzLCB3ZSBsb29rIGF0IHRoZSBjb3JyZWxhdGlvbnMgYmV0d2VlbiBiZXRhaGF0IGZyb20gZGF0YXNldCBBIGFuZCBiZXRhaGF0IGZyb20gZGF0YXNldCBCIGZvciB0aGUgdW5hZGp1c3RlZCBtZXRob2QsIFJVVmludiBhbmQgUlVWNC4KCmBgYHtyIGNvci1iZXRhaGF0LUEtQi1IS30KIyMtLS0tLS0gVW5hZGp1c3RlZCBkYXRhIHNldHMKcGxvdChmaXRfdW5hZGpfaGtfZGF0YXNldEEkYmV0YWhhdCwgCiAgICAgZml0X3VuYWRqX2hrX2RhdGFzZXRCJGJldGFoYXQsCiAgICAgeGxhYiA9ICJCZXRhaGF0IGRhdGFzZXQgQSIsCiAgICAgeWxhYiA9ICJCZXRhaGF0IGRhdGFzZXQgQiIsCiAgICAgbWFpbiA9ICJVbmFkanVzdGVkIiwKICAgICB4bGltID0gYygtMywzKSwgY2V4ID0gMC4zLCB5bGltID0gYygtNCw0KSkKY29yVmFsIDwtIGNvci50ZXN0KGZpdF91bmFkal9oa19kYXRhc2V0QSRiZXRhaGF0LCBmaXRfdW5hZGpfaGtfZGF0YXNldEIkYmV0YWhhdCkkZXN0aW1hdGUKdGV4dCgtMywzLCBwb3MgPSA0LCBwYXN0ZSgiQ29ycmVsYXRpb246ICIsIHJvdW5kKGNvclZhbCwyKSwgc2VwID0gIiIpKQoKCmZvciAoSyBpbiBrcyl7CiAgIAogICMtLS0tLS0tIFJVVjQgYWRqdXN0ZWQgZGF0YSBzZXRzCiAgcGxvdChmaXRfcnV2NF9oa19kYXRhc2V0QV9hbGxfa1tbS11dJGJldGFoYXQsCiAgICAgZml0X3J1djRfaGtfZGF0YXNldEJfYWxsX2tbW0tdXSRiZXRhaGF0LAogICAgIHhsYWIgPSAiQmV0YWhhdCBkYXRhc2V0IEEiLAogICAgIHlsYWIgPSAiQmV0YWhhdCBkYXRhc2V0IEIiLAogICAgIG1haW4gPSBwYXN0ZSgiUlVWNF9LXyIsSyxzZXA9IiIpLAogICAgIHhsaW0gPSBjKC0zLDMpLCBjZXggPSAwLjMsIHlsaW0gPSBjKC00LDQpKQogICNhYmxpbmUoZml0X3J1djRfZW1wX2RhdGFzZXRCJGJldGFoYXQsZml0X3J1djRfZW1wX2RhdGFzZXRBJGJldGFoYXQpCiAgY29yVmFsIDwtIGNvci50ZXN0KGZpdF9ydXY0X2hrX2RhdGFzZXRBX2FsbF9rW1tLXV0kYmV0YWhhdCwgZml0X3J1djRfaGtfZGF0YXNldEJfYWxsX2tbW0tdXSRiZXRhaGF0KSRlc3RpbWF0ZQogIHRleHQoLTMsMywgcG9zPTQsIHBhc3RlKCJDb3JyZWxhdGlvbjogIiwgcm91bmQoY29yVmFsLDIpLHNlcD0iIikpCn0KCmBgYAoKIyMgT3ZlcmxhcCBiZXR3ZWVuIGRpZmZlcmVudGlhbGx5IGV4cHJlc3NlZCBnZW5lcyAKRmluYWxseSwgZm9yIGVhY2ggb2YgdGhlIHVuYWRqdXN0ZWQsIFJVVmludiBhbmQgUlVWNCwgd2UgbG9vayBhdCB0aGUgbnVtYmVyIG9mIG92ZXJsYXBwaW5nIGRpZmZlcmVudGlhbGx5IGV4cHJlc3NlZCBnZW5lcyAoREVHcykgYmV0d2VlbiB0aGUgdHdvIGRhdGFzZXQgQSBhbmQgQiBkYXRhIHNldHMuIFdlIGFsc28gY2hlY2sgZm9yIGNvbnNpc3RlbmN5IGJldHdlZW4gbWV0aG9kcyBvbiB0aGUgc2FtZSBkYXRhIChkYXRhc2V0IEEgb3IgZGF0YXNldCBCIGRhdGEgc2V0KS5cCgpGaXJzdCwgd2UgZGVmaW5lIERFR3MgYXMgZ2VuZXMgd2l0aCBhZGp1c3RlZCBwLXZhbHVlIDwgMC4wNSBhbmQgfGxvZ0ZDfCA+IDEgaW4gZGF0YXNldCBBIGFuZCBCIGRhdGEgc2V0cyB3aGljaCBhcmUgdW5hZGp1c3RlZCwgUlVWNC0gb3IgUlVWaW52LWFkanVzdGVkLgoKYGBge3J9Cks9MjMKIyMtLS0tLS0gSW4gZGF0YXNldCBBIGRhdGEKREVHc1VuYWRqX2RhdGFzZXRBIDwtIHJvdy5uYW1lcyhmaXRfdW5hZGpfaGtfZGF0YXNldEEuc3VtbWFyeSRDKVtmaXRfdW5hZGpfaGtfZGF0YXNldEEuc3VtbWFyeSRDJEYucC5CSCA8IDAuMDUgJiBhYnMoZml0X3VuYWRqX2hrX2RhdGFzZXRBLnN1bW1hcnkkQyRiX1gxKSA+IDFdCgpERUdzUlVWNF9kYXRhc2V0QSA8LSByb3cubmFtZXMoZml0X3J1djRfaGtfZGF0YXNldEFfYWxsX2suc3VtbWFyeVtbS11dJEMpW2ZpdF9ydXY0X2hrX2RhdGFzZXRBX2FsbF9rLnN1bW1hcnlbW0tdXSRDJEYucC5CSCA8IDAuMDUgJiBhYnMoZml0X3J1djRfaGtfZGF0YXNldEFfYWxsX2suc3VtbWFyeVtbS11dJEMkYl9YMSkgPiAxXSAgCgpERUdzUlVWNF9kYXRhc2V0QV9hbGxfaz1saXN0KCkKZm9yIChLIGluIGtzKXsKICBERUdzUlVWNF9kYXRhc2V0QV9hbGxfa1tbS11dPC0gcm93Lm5hbWVzKGZpdF9ydXY0X2hrX2RhdGFzZXRBX2FsbF9rLnN1bW1hcnlbW0tdXSRDKVtmaXRfcnV2NF9oa19kYXRhc2V0QV9hbGxfay5zdW1tYXJ5W1tLXV0kQyRGLnAuQkggPCAwLjA1ICYgYWJzKGZpdF9ydXY0X2hrX2RhdGFzZXRBX2FsbF9rLnN1bW1hcnlbW0tdXSRDJGJfWDEpID4gMV0gIAp9CgojIy0tLS0tLSBJbiBkYXRhc2V0IEIgZGF0YToKREVHc1VuYWRqX2RhdGFzZXRCIDwtIHJvdy5uYW1lcyhmaXRfdW5hZGpfaGtfZGF0YXNldEIuc3VtbWFyeSRDKVtmaXRfdW5hZGpfaGtfZGF0YXNldEIuc3VtbWFyeSRDJEYucC5CSCA8IDAuMDUgJiBhYnMoZml0X3VuYWRqX2hrX2RhdGFzZXRCLnN1bW1hcnkkQyRiX1gxKSA+IDFdCgoKREVHc1JVVjRfZGF0YXNldEIgPC0gcm93Lm5hbWVzKGZpdF9ydXY0X2hrX2RhdGFzZXRCX2FsbF9rLnN1bW1hcnlbW0tdXSRDKVtmaXRfcnV2NF9oa19kYXRhc2V0Ql9hbGxfay5zdW1tYXJ5W1tLXV0kQyRGLnAuQkggPCAwLjA1ICYgYWJzKGZpdF9ydXY0X2hrX2RhdGFzZXRCX2FsbF9rLnN1bW1hcnlbW0tdXSRDJGJfWDEpID4gMV0gIAoKREVHc1JVVjRfZGF0YXNldEJfYWxsX2s9bGlzdCgpCmZvciAoSyBpbiBrcyl7CiAgREVHc1JVVjRfZGF0YXNldEJfYWxsX2tbW0tdXTwtIHJvdy5uYW1lcyhmaXRfcnV2NF9oa19kYXRhc2V0Ql9hbGxfay5zdW1tYXJ5W1tLXV0kQylbZml0X3J1djRfaGtfZGF0YXNldEJfYWxsX2suc3VtbWFyeVtbS11dJEMkRi5wLkJIIDwgMC4wNSAmIGFicyhmaXRfcnV2NF9oa19kYXRhc2V0Ql9hbGxfay5zdW1tYXJ5W1tLXV0kQyRiX1gxKSA+IDFdICAKfQpgYGAKCiMjIyBERUdzIGluIHRoZSB1bmFkanVzdGVkIGRhdGEKVmVubiBkaWFncmFtIGNvbXBhcmluZyB0aGUgdW5hZGp1c3RlZCBkYXRhc2V0IEEgYW5kIEIgZGF0YS4KYGBge3IgVmVubi1ERUdzLXVuYWRqfQphbGxERUdzX3VuYWRqIDwtIGMoREVHc1VuYWRqX2RhdGFzZXRBLCAKICAgICAgICAgICAgICAgICAgICBERUdzVW5hZGpfZGF0YXNldEIpCgojIyByZW1vdmUgZHVwbGljYXRlZCBnZW5lIHN5bWJvbHM6CmFsbERFR3NfdW5hZGogPC0gYWxsREVHc191bmFkalshZHVwbGljYXRlZChhbGxERUdzX3VuYWRqKV0gIAoKIyMgRHJhdyBhIFZlbm4gZGlhZ3JhbSBjb21wYXJpbmcgREVHcyBmb3IgUlVWaW52CkNvdW50c191bmFkaiA8LSBtYXRyaXgoMCwgbnJvdyA9IGxlbmd0aChhbGxERUdzX3VuYWRqKSwgbmNvbCA9IDIpCnJvdy5uYW1lcyhDb3VudHNfdW5hZGopPC0gYWxsREVHc191bmFkagpjb2xuYW1lcyhDb3VudHNfdW5hZGopPC0gYygiVW5hZGpfQSIsIlVuYWRqX0IiKQoKZm9yKCBpIGluIDE6bGVuZ3RoKGFsbERFR3NfdW5hZGopKSB7CiAgQ291bnRzX3VuYWRqW2ksMV08LSBhbGxERUdzX3VuYWRqW2ldICVpbiUgREVHc1VuYWRqX2RhdGFzZXRBCiAgQ291bnRzX3VuYWRqW2ksMl08LSBhbGxERUdzX3VuYWRqW2ldICVpbiUgREVHc1VuYWRqX2RhdGFzZXRCCn0KCmNvbCA8LSBjKCJibHVlIiwgInZpb2xldCIpCnZlbm5EaWFncmFtKHZlbm5Db3VudHMoQ291bnRzX3VuYWRqKSwgCiAgICAgICAgICAgIGNpcmNsZS5jb2wgPSBjb2wsIAogICAgICAgICAgICBjZXggPSBjKDEuNiwgMS4yLCAxKSwgbHdkPTIpCgpgYGAKCgojIyMgREVHcyBpbiB0aGUgUlVWNC1hZGp1c3RlZCBkYXRhIGZvciBkaWZmZXJlbnQgawpWZW5uIGRpYWdyYW0gY29tcGFyaW5nIHRoZSBSVVY0LWFkanVzdGVkIGRhdGFzZXQgQSBhbmQgQiBkYXRhLgpgYGB7ciBWZW5uLURFR3MtUlVWNH0KIyAKIyBhbGxERUdzX1JVVjQ8LSBjKERFR3NSVVY0X2RhdGFzZXRBLCBERUdzUlVWNF9kYXRhc2V0QikKIyAjIyByZW1vdmUgZHVwbGljYXRlZCBnZW5lIHN5bWJvbHM6CiMgYWxsREVHc19SVVY0PC0gYWxsREVHc19SVVY0WyFkdXBsaWNhdGVkKGFsbERFR3NfUlVWNCldICAKIyAjIyBEcmF3IGEgVmVubiBkaWFncmFtIGNvbXBhcmluZyBERUdzIGZvciBSVVY0CiMgQ291bnRzX1JVVjQgPC0gbWF0cml4KDAsIG5yb3c9IGxlbmd0aChhbGxERUdzX1JVVjQpLCBuY29sPTIpCiMgcm93Lm5hbWVzKENvdW50c19SVVY0KTwtIGFsbERFR3NfUlVWNAojIGNvbG5hbWVzKENvdW50c19SVVY0KTwtIGMoIlJVVjRfQSIsIlJVVjRfQiIpCiMgCiMgZm9yKCBpIGluIDE6bGVuZ3RoKGFsbERFR3NfUlVWNCkpIHsKIyAgIENvdW50c19SVVY0W2ksMV08LSBhbGxERUdzX1JVVjRbaV0gJWluJSBERUdzUlVWNF9kYXRhc2V0QQojICAgQ291bnRzX1JVVjRbaSwyXTwtIGFsbERFR3NfUlVWNFtpXSAlaW4lIERFR3NSVVY0X2RhdGFzZXRCCiMgfQojIAojIGNvbDwtIGMoImJsdWUiLCAidmlvbGV0IikKIyB2ZW5uRGlhZ3JhbSh2ZW5uQ291bnRzKENvdW50c19SVVY0KSwgCiMgICAgICAgICAgICAgY2lyY2xlLmNvbCA9IGNvbCwgCiMgICAgICAgICAgICAgY2V4ID0gYygxLjYsIDEuMiwgMSksIGx3ZCA9IDIpCgphbGxERUdzX1JVVjRfYWxsX2s9bGlzdCgpCmZvciAoSyBpbiBrcyl7CiAgYWxsREVHc19SVVY0X2FsbF9rW1tLXV09YyhERUdzUlVWNF9kYXRhc2V0QV9hbGxfa1tbS11dLERFR3NSVVY0X2RhdGFzZXRCX2FsbF9rW1tLXV0pCiAgIyMgcmVtb3ZlIGR1cGxpY2F0ZWQgZ2VuZSBzeW1ib2xzOgogIGFsbERFR3NfUlVWNF9hbGxfa1tbS11dPC0gYWxsREVHc19SVVY0X2FsbF9rW1tLXV1bIWR1cGxpY2F0ZWQoYWxsREVHc19SVVY0X2FsbF9rW1tLXV0pXSAgCiAgIyMgRHJhdyBhIFZlbm4gZGlhZ3JhbSBjb21wYXJpbmcgREVHcyBmb3IgUlVWNAogIENvdW50c19SVVY0PC0gbWF0cml4KDAsIG5yb3c9IGxlbmd0aChhbGxERUdzX1JVVjRfYWxsX2tbW0tdXSksIG5jb2w9MikKICByb3cubmFtZXMoQ291bnRzX1JVVjQpPC0gYWxsREVHc19SVVY0X2FsbF9rW1tLXV0KICBjb2xuYW1lcyhDb3VudHNfUlVWNCk8LSBjKHBhc3RlKCJSVVY0X0FfS18iLEssc2VwPSIiKSxwYXN0ZSgiUlVWNF9CX0tfIixLLHNlcD0iIikpCgogIGZvciggaSBpbiAxOmxlbmd0aChhbGxERUdzX1JVVjRfYWxsX2tbW0tdXSkpIHsKICAgIENvdW50c19SVVY0W2ksMV08LSBhbGxERUdzX1JVVjRfYWxsX2tbW0tdXVtpXSAlaW4lIERFR3NSVVY0X2RhdGFzZXRBX2FsbF9rW1tLXV0KICAgIENvdW50c19SVVY0W2ksMl08LSBhbGxERUdzX1JVVjRfYWxsX2tbW0tdXVtpXSAlaW4lIERFR3NSVVY0X2RhdGFzZXRCX2FsbF9rW1tLXV0KICB9CgogIGNvbDwtIGMoImJsdWUiLCAidmlvbGV0IikKICB2ZW5uRGlhZ3JhbSh2ZW5uQ291bnRzKENvdW50c19SVVY0KSwgCiAgICAgICAgICAgIGNpcmNsZS5jb2wgPSBjb2wsIAogICAgICAgICAgICBjZXggPSBjKDEuNiwgMS4yLCAxKSwgbHdkID0gMikKfQoKYGBgCgojIyMgQ29tcGFyZSB0aGUgdW5hZGp1c3RlZCBhbmQgUlVWNCBpbiBkYXRhc2V0IEEgZGF0YQpgYGB7ciBWZW5uLURFR3MtZGF0YXNldEF9Cks9MjMKYWxsREVHc19kYXRhc2V0QSA8LSBjKERFR3NVbmFkal9kYXRhc2V0QSwgIERFR3NSVVY0X2RhdGFzZXRBX2FsbF9rW1tLXV0pCgojIyByZW1vdmUgZHVwbGljYXRlZCBnZW5lIHN5bWJvbHM6CmFsbERFR3NfZGF0YXNldEEgPC0gYWxsREVHc19kYXRhc2V0QVshZHVwbGljYXRlZChhbGxERUdzX2RhdGFzZXRBKV0gIAoKIyMgRHJhdyBhIFZlbm4gZGlhZ3JhbSBjb21wYXJpbmcgREVHcyBmb3IgZGF0YXNldCBBCkNvdW50c19kYXRhc2V0QSA8LSBtYXRyaXgoMCwgbnJvdz0gbGVuZ3RoKGFsbERFR3NfZGF0YXNldEEpLCBuY29sPTIpCnJvdy5uYW1lcyhDb3VudHNfZGF0YXNldEEpPC0gYWxsREVHc19kYXRhc2V0QQpjb2xuYW1lcyhDb3VudHNfZGF0YXNldEEpPC0gYygiVW5hZGpfQSIsICJSdXY0X0FfS18yMyIpCgpmb3IoIGkgaW4gMTpsZW5ndGgoYWxsREVHc19kYXRhc2V0QSkpIHsKICBDb3VudHNfZGF0YXNldEFbaSwxXTwtIGFsbERFR3NfZGF0YXNldEFbaV0gJWluJSBERUdzVW5hZGpfZGF0YXNldEEKICBDb3VudHNfZGF0YXNldEFbaSwyXTwtIGFsbERFR3NfZGF0YXNldEFbaV0gJWluJSBERUdzUlVWNF9kYXRhc2V0QV9hbGxfa1tbS11dCn0KCmNvbDwtIGMoImJsdWUiLCJkYXJrZ3JlZW4iKQp2ZW5uRGlhZ3JhbSh2ZW5uQ291bnRzKENvdW50c19kYXRhc2V0QSksIAogICAgICAgICAgICBjaXJjbGUuY29sPWNvbCwgCiAgICAgICAgICAgIGNleD1jKDEuNiwgMS4yLCAxKSwgbHdkPTIpCgpgYGAKCiMjIyBDb21wYXJlIHRoZSB1bmFkanVzdGVkIGFuZCBSVVY0IGluIGRhdGFzZXQgQiBkYXRhCmBgYHtyIFZlbm4tREVHcy1kYXRhc2V0Qn0KSz0yMwphbGxERUdzX2RhdGFzZXRCIDwtIGMoREVHc1VuYWRqX2RhdGFzZXRCLERFR3NSVVY0X2RhdGFzZXRCX2FsbF9rW1tLXV0pCgojIyByZW1vdmUgZHVwbGljYXRlZCBnZW5lIHN5bWJvbHM6CmFsbERFR3NfZGF0YXNldEIgPC0gYWxsREVHc19kYXRhc2V0QlshZHVwbGljYXRlZChhbGxERUdzX2RhdGFzZXRCKV0gCgojIyBEcmF3IGEgVmVubiBkaWFncmFtIGNvbXBhcmluZyBERUdzIGZvciBkYXRhc2V0IEIKQ291bnRzX2RhdGFzZXRCIDwtIG1hdHJpeCgwLCBucm93ID0gbGVuZ3RoKGFsbERFR3NfZGF0YXNldEIpLCBuY29sID0gMikKcm93Lm5hbWVzKENvdW50c19kYXRhc2V0QikgPC0gYWxsREVHc19kYXRhc2V0Qgpjb2xuYW1lcyhDb3VudHNfZGF0YXNldEIpIDwtIGMoIlVuYWRqX0IiLCAiUnV2NF9CX0tfMjMiKQoKZm9yKCBpIGluIDE6bGVuZ3RoKGFsbERFR3NfZGF0YXNldEIpKSB7CiAgQ291bnRzX2RhdGFzZXRCW2ksMV08LSBhbGxERUdzX2RhdGFzZXRCW2ldICVpbiUgREVHc1VuYWRqX2RhdGFzZXRCCiAgQ291bnRzX2RhdGFzZXRCW2ksMl08LSBhbGxERUdzX2RhdGFzZXRCW2ldICVpbiUgREVHc1JVVjRfZGF0YXNldEJfYWxsX2tbW0tdXQp9Cgpjb2wgPC0gYygiYmx1ZSIsICJkYXJrZ3JlZW4iKQp2ZW5uRGlhZ3JhbSh2ZW5uQ291bnRzKENvdW50c19kYXRhc2V0QiksIAogICAgICAgICAgICBjaXJjbGUuY29sID0gY29sLCAKICAgICAgICAgICAgY2V4ID0gYygxLjYsIDEuMiwgMSksIGx3ZCA9IDIpCmBgYAoKCgoKCgo=